Cache memories improve memory access performance of a computer based on temporal locality of access in which once-accessed data is likely to be accessed again and spatial locality of access in which it is highly probable that data close to the once-accessed data will be accessed. The capacity of a cache memory is, however, limited. Accordingly, it is necessary to efficiently utilize the limited capacity to improve a cache hit ratio. A location of the cache memory where a block to be cached is stored differs according to the mapping method of the cache memory.
In a full associative method, each block can be stored in any location of a cache memory. Thus, the cache memory can be efficiently utilized. In the full associative method, however, when searching whether or not there is a block in the cache, all blocks in the cache must be searched. Accordingly, it takes time to perform the search.
A direct mapping method is a method by which a search within a cache memory can be performed most simply. In the direct mapping method, a location where each block is stored is limited to a predetermined portion of the cache memory. In the direct mapping method, however, the location where each block is stored is fixed. Accordingly, a plurality of blocks to be stored in a same location cannot be simultaneously cached in the cache memory.
An N-way set associative method is intermediate between these two methods. In the N-way set associative method, there are N locations for storing a certain block, in a cache memory. That is, N blocks to be stored in a same location in the cache memory can be simultaneously cached. Further, when it is searched whether or not a block has been cached in the cache memory, N locations should be searched.
Patent Document 1 describes a victim cache memory for storing a block targeted for replacement and evicted from a cache memory so as to cache another block when a cache miss has occurred. The victim cache in Patent Document 1 is a cache of a small capacity (of several blocks) using the full associative method, and caches a block evicted from the cache memory. When a block in the victim cache memory has resulted in a cache hit, an evicted block and the block which has resulted in the cache hit are swapped (exchanged) between the cache memory and the victim memory.    Patent Document 1: JP Patent Kokai Publication No. JP-A-4-270431